#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void dfs(vector<vector<int>> &gh, vector<int> &vis, int u, vector<int> &path)
{
        vis[u] = 1;
        path.push_back(u);
        for(auto v : gh[u]){
                if(!vis[v]){
                        dfs(gh, vis, v, path);
                }
        }
}

void bfs(vector<vector<int>> &gh, vector<int> &vis, int u, vector<int> &path)
{
        queue<int> q;
        q.push(u);
        vis[u] = 1;

        while(!q.empty()){
                int u = q.front();
                q.pop();
                path.push_back(u);
                for(auto v : gh[u]){
                        if(!vis[v]){
                                vis[v] = 1;
                                q.push(v);
                        }
                }
        }
}

int main()
{
        int n, m;
        cin >> n >> m;
        vector<vector<int>> gh(n + 1);
        for(int i = 0; i < m; i++){
                int u, v;
                cin >> u >> v;
                gh[u].push_back(v);
        }
        for(int i = 1; i <= n; i++){
                sort(gh[i].begin(), gh[i].end());
        }
        
        vector<int> path, vis(n + 1, 0);
        dfs(gh, vis, 1, path);
        for(auto u : path){
                cout << u << " ";
        }
        cout<<endl;

        fill(vis.begin(), vis.end(), 0);
        path.resize(0);
        bfs(gh, vis, 1, path);
        for(auto u : path){
                cout << u << " ";
        }
        cout<<endl;
        return 0;
}